// https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/description/

// 算法思路总结：
// 1. 记忆化搜索求解矩阵中的最长递增路径
// 2. 从每个单元格出发，递归向四个方向扩展
// 3. 只能向值更大的相邻单元格移动
// 4. memo[a][b]记录从(a,b)出发的最长路径长度
// 5. 时间复杂度：O(m×n)，空间复杂度：O(m×n)

#include <iostream>
using namespace std;

#include <vector>
#include <cstring>
#include <algorithm>

class Solution 
{
public:
    int m, n;
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    int memo[201][201];

    int longestIncreasingPath(vector<vector<int>>& matrix) 
    {
        m = matrix.size(), n = matrix[0].size();
        memset(memo, -1, sizeof(memo));

        int ret = 0;
        for (int i = 0 ; i < m ; i++)
        {
            for (int j = 0 ; j < n ; j++)
            {
                ret = max(ret, dfs(matrix, i, j));
            }
        }

        return ret;
    }

    int dfs(vector<vector<int>>& matrix, int a, int b)
    {
        if (memo[a][b] != -1)
            return memo[a][b];

        int ret = 1;
        for (int i = 0 ; i < 4 ; i++)
        {
            int x = a + dx[i], y = b + dy[i];
            if (x >= 0 && y >= 0 && x < m && y < n && matrix[x][y] > matrix[a][b])
            {
                ret = max(ret, dfs(matrix, x, y) + 1);
            }
        }

        return memo[a][b] = ret;
    }
};

int main()
{
    Solution sol;

    vector<vector<int>> matrix1 = {
        {9, 9, 4},
        {6, 6, 8},
        {2, 1, 1}
    };

    vector<vector<int>> matrix2 = {
        {3, 4, 5},
        {3, 2, 6},
        {2, 2, 1}
    };

    cout << sol.longestIncreasingPath(matrix1) << endl;
    cout << sol.longestIncreasingPath(matrix2) << endl;

    return 0;
}